//
// Created by PC on 2024/4/26.
//

#include "arrUtil.h"
#include <iostream>

using namespace std;

vector<int> merge(vector<int> l, vector<int> r)
{
    int i = 0, j = 0;
    vector<int> ret;
    while (i < l.size() && j < r.size())
    {
        if (l[i] <= r[j])
        {
            ret.push_back(l[i]);
            ++i;
        } else
        {
            ret.push_back(r[j]);
            ++j;
        }
    }
    while (i < l.size())
    {
        ret.push_back(l[i]);
        ++i;
    }
    while (j < r.size())
    {
        ret.push_back(r[j]);
        ++j;
    }
    return ret;
}

vector<int> mergeSort(vector<int> vv)
{
    if (vv.size() > 1)
    {
        vector<int> left, right;
        int m = vv.size() / 2;
        for (int i = 0; i < m; ++i)
            left.push_back(vv[i]);
        for (int i = m; i < vv.size(); ++i)
            right.push_back(vv[i]);
        return merge(mergeSort(left),mergeSort(right));
    }
    return vv;
}

int main()
{
//    vector<int> v1{1, 3, 5, 8};
//    vector<int> v2{2, 4, 6, 9};
//    vector<int> nv = merge(v1, v2);
//    printVector(nv);
    vector<int> v = {0,9,8,7,5,4,3,0,3,2};
    randVector(v,1000);
    vector<int> nv = mergeSort(v);
    cout<<checkSortVector(nv);
    return 0;
}